package may;

import sun.nio.cs.ext.MacThai;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-2 12:42
 * @description：
 * @modified By：
 * @version:
 */
public class May02 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
     * 使用动态规划
     * 1. cash存我卖出当前持有的股票的收益的最大值
     * 2. hold存我买入股票时的最大收益
     * 我们将length天的问题化成每一天我如何去获取最大收益
     * 对于每天的股票有两个选择卖出上一次买入的股票 或者 买入今天的股票
     * 对于cash我们可以选择什么都不做 或者 卖出上次买入的股票
     * 对于hold 我们也可以选择什么都不买或者 买入今天的股票
     * 之所以是先计算cash再计算hold 是因为 在同一天买入一个股票和卖出当天的股票是一定会亏损手续费的 所以要先计算卖出上一次买入的股票能否赚钱 在考虑买新的
     * create time: 2020-5-2 12:43
     * @params [prices, fee]
     * @return int
     */
    public int maxProfit(int[] prices, int fee) {

        int cash = 0, hold = -prices[0]; //初始化 先买入第一天的股票
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(cash, hold + prices[i] - fee); //计算在每一天卖出能赚到的最大值
            hold = Math.max(hold, cash - prices[i]); //用那天卖出的价格去选择是否买入今天的股票
        }
        return cash;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
     * create time: 2020-5-2 13:58
     * @params [s]
     * @return int
     */
    public int lengthOfLongestSubstring(String s) {

        char[] list = s.toCharArray();
        int start = 0;
        int end  = 0;
        Map<Character,Integer> map = new HashMap<>();
        int max = 0;
        for (; end < list.length; end++) {
            char c = list[end];
            if(map.containsKey(c)){
                //如果有这个字符 就需要看这个字符是在当前的start之前还是之后 如果在之前就证明 这个字符其实已经被淘汰了无所谓 在之后就证明
                //有重复的字符在我们子列中所以 我们将start放到第一个重复字符的下一个位置
                start = Math.max(start,map.get(c));
            }
            max = Math.max(max,end-start+1);
            map.put(c,end+1); //这里记录每一个字符的后一个位置 以便start移动
        }
        return max;
    }
}
